import functools


class Solution:
    """
    【取值范围】
    1 <= k <= 5
    1 <= n <= 130

    【时间复杂度】
    按当前有0个、1个、2个、3个、4个、5个字母对字母进行分类，共有：C(32,6)=906192
    """

    _MOD = 10 ** 9 + 7

    def keyboard(self, k: int, n: int) -> int:
        k1 = 26 if k == 1 else 0
        k2 = 26 if k == 2 else 0
        k3 = 26 if k == 3 else 0
        k4 = 26 if k == 4 else 0
        k5 = 26 if k == 5 else 0
        return self.dfs(n, k1, k2, k3, k4, k5)

    @functools.lru_cache(None)
    def dfs(self, n, k1, k2, k3, k4, k5):
        if n == 0:
            return 1

        ans = 0

        if k5 > 0:
            ans += k5 * self.dfs(n - 1, k1, k2, k3, k4 + 1, k5 - 1) % self._MOD
        if k4 > 0:
            ans += k4 * self.dfs(n - 1, k1, k2, k3 + 1, k4 - 1, k5) % self._MOD
        if k3 > 0:
            ans += k3 * self.dfs(n - 1, k1, k2 + 1, k3 - 1, k4, k5) % self._MOD
        if k2 > 0:
            ans += k2 * self.dfs(n - 1, k1 + 1, k2 - 1, k3, k4, k5) % self._MOD
        if k1 > 0:
            ans += k1 * self.dfs(n - 1, k1 - 1, k2, k3, k4, k5) % self._MOD

        return ans % self._MOD


if __name__ == "__main__":
    print(Solution().keyboard(1, 1))  # 26
    print(Solution().keyboard(1, 2))  # 650
